COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a03.tex[106,phy] \today\hfill}

\bigskip
\line{\hfill CS 106}
\line{\hfill Feb.\ 22, 1984}
\bigskip
\centerline{Computation by Problem Size Reduction}

\bigskip
A powerful paradigm of programming reduces a problem to a simpler one,
repeating this until the reduced problem has a direct solution. A~program
based on this paradigm must be able later to work back through the sequence
of problems, completing their solutions. An example from the calculus
is integrating $\int x↑ne↑{-x↑2}\,dx$ by parts; $d(e↑{-x↑2})=-2xe↑{-x↑2}\,dx$,
so
$$\eqalign{\int↓a↑bx↑ne↑{-x↑2}\,dx&=-{1\over 2}\int↓a↑bx↑{n-1}d(e↑{-x↑2})\cr
\noalign{\smallskip}
&=-{1\over 2}\bigl(x↑{n-1}e↑{-x↑2}\bigr)|↓a↑b+{1\over 2}\int↓a↑be↑{-x↑2}d(x↑{n-1})\cr
\noalign{\smallskip}
&=-{1\over 2}\bigl(x↑{n-1}e↑{-x↑2}\bigr)↓a↑b+{n-1\over 2}\int↓a↑bx↑{n-2}e↑{-x↑2}\,
dx\,.\cr}$$
If $n$ is odd, this eliminates the integration in $(n+1)/2$ steps, after which
one works back through the sequence of equations to the solution of the
original problem.

This approach is applied to solving the set of simultaneous linear equations.
$$\vcenter{\halign{$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$%
&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\lft{#}$\cr
a↓{11}x↓1&+&a↓{12}x↓2&+&\cdots&+&a↓{1n}x↓n&=&b↓1\cr
a↓{21}x↓1&+&a↓{22}x↓2&+&\cdots&+&a↓{2n}x↓n&=&b↓2\cr
\vdots&&\vdots&&\ddots&&\vdots&&\vdots\cr
a↓{n1}x↓1&+&a↓{n2}x↓2&+&\cdots&+&a↓{nn}x↓n&=&b↓2\cr}}$$
for $x↓1,x↓2,\ldots,x↓n$.

First, let's get rid of the $b$'s, by introducing a new variable $x↓0$
with known value~$-1$, and writing the equations as
$$\vcenter{\halign{$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$%
&$\ctr{#}\;$&$\ctr{#}\;$%
&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\lft{#}$\cr
a↓{10}x↓0&+&a↓{11}x↓1&+&a↓{12}x↓2&+&\cdots&+&a↓{1n}x↓n&=&0\cr
\vdots&&\vdots&&\vdots&&\ddots&&\vdots&&\vdots\cr
a↓{n0}x↓0&+&a↓{n1}x↓1&+&a↓{n2}x↓2&+&\cdots&+&a↓{nn}x↓n&=&0\cr}}$$
with $a↓{10}=b↓1$, $a↓{20}=b↓2$, etc.

We will change the equations to a new set with the same solutions, but
where the first $n-1$ equations no longer involve the last variable,~$x↓n$;
$a↓{1n},a↓{2n},\ldots,a↓{n-1,n}$ will all be zero.

We change the first equation by subtracting from it the last equation,
multiplied by $a↓{1n}/a↓{nn}$. This can't be done if $a↓{nn}=0$, so a
practical algorithm must be able to swap equations and/or variables
around; we'll assume, for simplicity, that the difficulty never arises on
the equations we want to solve. From the second equation, we subtract
the last equation multiplied by $a↓{2n}/a↓{nn}$, and so on. When done,
the equations are
$$\vcenter{\halign{$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$%
&$\ctr{#}\;$&$\ctr{#}\;$%
&$\ctr{#}\;$&$\ctr{#}\;$&$\ctr{#}\;$&$\lft{#}$\cr
a↓{10}x↓0&+&a↓{11}x↓1&+&a↓{12}x↓2&+&\cdots&+&a↓{1,n-1}x↓{n-1}(+0\,x↓n)&=&0\cr
\vdots&&\vdots&&\vdots&&\ddots&&\vdots&&\vdots\cr
a↓{n-1,0}x↓0&+&a↓{n-1,1}x↓1&+&a↓{n-1,2}x↓2&+&\cdots&+&a↓{n-1,n-1}x↓{n-1}(+0\,x↓n)&=&0\cr
a↓{n,0}x↓0&+&a↓{n1}x↓1&+&a↓{n2}x↓2&+&\cdots&+&a↓{n,n-1}x↓{n-1}+a↓{nn}x↓n&=&0\cr}}$$

In Pascal, the part of the algorithm that eliminates $x↓n$ from the first
$n-1$ equations is:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        FOR I:=1 TO N-1 DO (* EQUATION NUMBER I *)
            BEGIN
            MULT:=A[I,N]/A[N,N];
            FOR J:=0 TO N-1 DO
                A[I,J]:=A[I,J]-MULT*A[N,J];
            A[I,N]:=0
            END
}

\smallskip\noindent
The part that later solves for $x↓n$, after $x↓0,x↓1,\ldots,x↓{n-1}$
have all been given values that satisfy the first $n-1$ equations, is:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        SUM:=-A[N,0]; (* X[0]=-1 *)
        FOR J:=1 TO N-1 DO SUM:=SUM+X[J]*A[N,J];
        X[N]:=-SUM/A[N,N]
}

\smallskip
The whole algorithm, called Gaussian elimination for its inventor, Karl
Friedrich Gauss (1777--1855), follows:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        BEGIN
        (* Read in M, A[1,0],...,A[M,M] *);
        READ(M) (* NUMBER OF EQUATIONS *)
        FOR N:=1 TO M DO
            FOR I:=0 TO M DO
                READ(A[N,I]);
        FOR N:=M DOWN TO 1 DO (* ELIMINATE X[N] *)
            BEGIN
            FOR I:=1 TO N-1 DO (* EQUATION NUMBER I *)
                BEGIN
                MULT:=A[I,N]/A[N,N];
                FOR J:=0 TO N-1 DO (* NEW COEFFICIENT FOR X[J] *)
                    A[I,J]:=A[I,J]-MULT*A[N,J];
                A[I,N]:=0;
                END
            END;
            FOR N:=1 TO M DO (* FIND X[N] *)
                BEGIN
                SUM:=-A[N,0]; (* X[0]=-1 *);
                FOR J:=1 TO N-1 DO
                    SUM:=SUM+X[J]*A[N,J];
                X[N]:=-SUM/A[N,N]
                WRITELN('X[',N:1,']=',X[N])
                END
            END
}

\smallskip
The reader is being asked to study the above example, not because it is
a good way to solve equations (it~is), but because it is a good way
to design an algorithm. Algorithm designers ask themselves, ``Can I change
this problem into a smaller one in some systematic way? For example,
can I find one of the unknown quantities, and use its value to simplify
the problem.''

Another example on the same lines is solving a polynomial equation
$P↓n(x)=a↓nx↑n+a↓{n-1}x↑{n-1}$
$\null+\cdots +a↓0=0$. Such
an equation has $n$ different solutions (roots). If one can  be found,
say a number $x↓n$ such that $P↓n(x↓n)=0$, we can divide $P↓n$ by
$x-x↓n$ evenly, getting a new polynomial~$P↓{n-1}$; solving $P↓{n-1}=0$
gives the rest of the roots of~$P↓n=0$. The completion of the design of
the algorithm requires designing a method to compute a single root
of~$P↓n$, which is a topic for another course.

The paradigm of problem size reduction in general goes from a problem
of size~$N$, down through simpler problems of size $N-1$, $N-2$, etc.,
until a problem of an easy size (usually 0 or~1) is reached. At each
reduction, enough information must be saved to work back later to the
original problem.

\smallskip
\smallskip
\disleft 38pt::
{\bf Exercise:}

\disleft 38pt::
Program an algorithm to evaluate $\int↓a↑bx↑ne↑{-x↑2}\,dx$
for inputs $A$, $B$, and~$N$, where $N$ is a positive odd integer.
Can you do it without using arrays.?

\smallskip
\disleft 38pt::
{\bf Exercise:}

\disleft 38pt::
Modify the Gaussian elimination algorithm to exchange
a pair of equations before each elimination, making the absolute value
of $A[N,N]$ as large as possible. This avoids division by zero if it
can be avoided, and also makes the process more exact numerically.

\vfill\eject
\line{\sevenrm a03.tex[106,phy] \today\hfill}
\line{\hfill CS 106}
\line{\hfill Feb.\ 22, 1984}

\bigskip
\ctrline{For section on dynamic programming}

\bigskip
Compare the dynamic programming paradigm to the problem size reduction
paradigm. The problem size reduction paradigm works through a sequence
of smaller and smaller problems, each of which is eventually a contributor
to the solution of the original problem. The dynamic programming paradigm
works through a series of larger and larger problems, some of which may
not be helpful to solving the original problem.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft February 22, 1984

\bye